package slideWindow;

import java.util.HashMap;
import java.util.Map;

/**
 * @author pengfei.hpf
 * @date 2020/3/10
 * @verdion 1.0.0
 * 1100. Find K-Length Substrings With No Repeated Characters
 * Given a string S, return the number of substrings of length K with no repeated characters.
 *
 *
 *
 * Example 1:
 *
 * Input: S = "havefunonleetcode", K = 5
 * Output: 6
 * Explanation:
 * There are 6 substrings they are : 'havef','avefu','vefun','efuno','etcod','tcode'.
 * Example 2:
 *
 * Input: S = "home", K = 5
 * Output: 0
 * Explanation:
 * Notice K can be larger than the length of S. In this case is not possible to find any substring.
 *
 *
 * Note:
 *
 * 1 <= S.length <= 10^4
 * All characters of S are lowercase English letters.
 * 1 <= K <= 10^4
 */
public class NumKLenSubstrNoRepeats {
    public int numKLenSubstrNoRepeats(String S, int K) {
        if(S == null || S.length() == 0 || S.length() < K){
            return 0;
        }
        if(K <= 1){
            return S.length();
        }
        Map<Character, Integer> indexMap = new HashMap<>();
        int left = 0;
        int right = 0;
        char[] chars = S.toCharArray();
        int res = 0;
        while(right < chars.length){
            char c = chars[right];
            if(indexMap.containsKey(c)){
                //TODO: 滑动窗口时记得删掉左边的记录!!!!!
                int start = left;
                left = indexMap.get(c) + 1;
                while(start < left){
                    indexMap.remove(chars[start]);
                    start ++;
                }
            } else {
                if(right - left + 1 == K){
                    res ++;
                    indexMap.remove(chars[left]);
                    left ++;
                }
            }
            indexMap.put(c, right);
            right ++;
        }
        return res;
    }

    public static void main(String[] args){
        System.out.println((new NumKLenSubstrNoRepeats()).numKLenSubstrNoRepeats("nonleetcode", 5));
    }
}
